package argo.hot100.graph;

import java.util.LinkedList;
import java.util.Queue;

public class OrangesRotting {

    public int orangesRotting(int[][] grid) {

        int rightCount = 0, cycleM = 0;
        Queue<int[]> queue = new LinkedList<>();

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    rightCount++;
                } else if (grid[i][j] == 2) {
                    queue.add(new int[]{i, j});
                }
            }
        }

        while (rightCount > 0 && !queue.isEmpty()) {
            int size = queue.size();
            cycleM++;
            for (int i = 0; i < size; i++) {
                int[] badInx = queue.poll();
                int x = badInx[0];
                int y = badInx[1];

                if (x - 1 >= 0 && grid[x - 1][y] == 1) {
                    grid[x - 1][y] = 2;
                    queue.add(new int[]{x - 1, y});
                    rightCount--;
                }
                if (y - 1 >= 0 && grid[x][y - 1] == 1) {
                    grid[x][y - 1] = 2;
                    queue.add(new int[]{x, y - 1});
                    rightCount--;

                }
                if (x + 1 < grid.length && grid[x + 1][y] == 1) {
                    grid[x + 1][y] = 2;
                    queue.add(new int[]{x + 1, y});
                    rightCount--;

                }
                if (y + 1 < grid[0].length && grid[x][y + 1] == 1) {
                    grid[x][y + 1] = 2;
                    queue.add(new int[]{x, y + 1});
                    rightCount--;

                }

            }
        }

        return rightCount == 0 ? cycleM : -1;


    }


}
